// 版权归Go作者所有。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 地址范围数据结构。
// 
// 此文件包含一个数据结构的实现，
// 用于管理有序地址范围。

package runtime

import (
	"runtime/internal/sys"
	"unsafe"
)

// addrRange表示地址空间的一个区域。
// 
// 地址安排不能跨越地址空间中的间隙。
type addrRange struct {
	// 基和极限一起表示地址空间的区域
	// [base，limit]。也就是说，base是包含的，limit是独占的。
	// 这些是地址空间偏移视图上的地址，在
	// 具有分段地址空间的平台上，也就是说，在平台上
	// 其中arenaBaseOffset！=0。
	base, limit offAddr
}

// makeAddrRange从2创建一个新的地址范围虚拟地址。
// 
// 如果基和限制不在同一内存段中，则抛出。
func makeAddrRange(base, limit uintptr) addrRange {
	r := addrRange{offAddr{base}, offAddr{limit}}
	if (base-arenaBaseOffset >= base) != (limit-arenaBaseOffset >= limit) {
		throw("addr range base and limit are not in the same memory segment")
	}
	return r
}

// size返回以字节表示的范围大小。
func (a addrRange) size() uintptr {
	if !a.base.lessThan(a.limit) {
		return 0
	}
	// 减法是安全的，因为限制和基必须在地址空间的同一
	// 段中。
	return a.limit.diff(a.base)
}

// contains返回该范围是否包含给定地址。
func (a addrRange) contains(addr uintptr) bool {
	return a.base.lessEqual(offAddr{addr}) && (offAddr{addr}).lessThan(a.limit)
}

// subtract将ADDRANGE设置为RUNE并从中删除与
// 的任何重叠，然后返回新的范围。subtract假设a和b 
// 要么完全不重叠，要么只在一侧重叠，要么相等。
// If b严格包含在a中，因此强制拆分，它将抛出。
func (a addrRange) subtract(b addrRange) addrRange {
	if b.base.lessEqual(a.base) && a.limit.lessEqual(b.limit) {
		return addrRange{}
	} else if a.base.lessThan(b.base) && b.limit.lessThan(a.limit) {
		throw("bad prune")
	} else if b.limit.lessThan(a.limit) && a.base.lessThan(b.limit) {
		a.base = b.limit
	} else if a.base.lessThan(b.base) && b.base.lessThan(a.limit) {
		a.limit = b.base
	}
	return a
}

// RemoveCreateRequal将大于或等于
// 中的所有地址删除到addr并返回新范围。
func (a addrRange) removeGreaterEqual(addr uintptr) addrRange {
	if (offAddr{addr}).lessEqual(a.base) {
		return addrRange{}
	}
	if a.limit.lessEqual(offAddr{addr}) {
		return a
	}
	return makeAddrRange(a.base.addr(), addr)
}

var (
	// MINOFADDR是偏移空间中的最小地址，
	// 它对应于虚拟地址arenaBaseOffset.
	minOffAddr = offAddr{arenaBaseOffset}

	// maxOffAddr是偏移地址
	// 空间中的最大地址。它对应于页面alloc区块和堆竞技场映射可表示的最高虚拟地址
	// 的地址。
	maxOffAddr = offAddr{(((1 << heapAddrBits) - 1) + arenaBaseOffset) & uintptrMask}
)

// offAddr表示地址的连续视图
// 中的地址地址空间为分段的系统上的ss空间。在其他系统上，它只是一个普通地址。
type offAddr struct {
	// a只是虚拟地址，但绝对不能直接使用
	// 调用addr（）改为获取此值。
	a uintptr
}

// add将uintptr偏移量添加到offAddr。
func (l offAddr) add(bytes uintptr) offAddr {
	return offAddr{a: l.a + bytes}
}

// sub从offAddr中减去uintptr偏移量。
func (l offAddr) sub(bytes uintptr) offAddr {
	return offAddr{a: l.a - bytes}
}

// diff返回两个offAddr之间的字节数。
func (l1 offAddr) diff(l2 offAddr) uintptr {
	return l1.a - l2.a
}

// 如果偏移量中的l1小于l2，则返回true
func (l1 offAddr) lessThan(l2 offAddr) bool {
	return (l1.a - arenaBaseOffset) < (l2.a - arenaBaseOffset)
}

// 如果偏移地址空间中的l1小于或等于l2，则lessEqual返回true。
// 如果两个offAddr值相等，则equal返回true。
func (l1 offAddr) lessEqual(l2 offAddr) bool {
	return (l1.a - arenaBaseOffset) <= (l2.a - arenaBaseOffset)
}

func (l1 offAddr) equal(l2 offAddr) bool {
	// 无需在偏移空间中进行比较，这与
	// 的含义相同。
	return l1 == l2
}

// addr返回此偏移地址的虚拟地址。
func (l offAddr) addr() uintptr {
	return l.a
}

// addranges是一个数据结构，包含一系列
// 地址空间。
// 
// 这些范围急切地合并在一起，以减少它所拥有的
// 数量范围。
// 
// 此字段的片备份存储是持久允许的
// 因此无法释放它。
// 
// ADDRANGES不是线程安全的。
type addrRanges struct {
	// ranges是按基排序的范围片。
	ranges []addrRange

	// totalBytes是以字节为单位的地址空间总量y 
	// this addrRanges.
	totalBytes uintptr

	// sysStat是跟踪此类型分配的stat 
	sysStat *sysMemStat
}

func (a *addrRanges) init(sysStat *sysMemStat) {
	ranges := (*notInHeapSlice)(unsafe.Pointer(&a.ranges))
	ranges.len = 0
	ranges.cap = 16
	ranges.array = (*notInHeap)(persistentalloc(unsafe.Sizeof(addrRange{})*uintptr(ranges.cap), sys.PtrSize, sysStat))
	a.sysStat = sysStat
	a.totalBytes = 0
}

// findSucc返回a中的第一个索引，使得addr是
// 小于该索引处addrRange的基数。
func (a *addrRanges) findSucc(addr uintptr) int {
	base := offAddr{addr}

	// 通过二进制搜索缩小搜索空间
	// 在我们最多剩下iterMax 
	// 候选者之前，进行大规模的额外安排。
	const iterMax = 8
	bot, top := 0, len(a.ranges)
	for top-bot > iterMax {
		i := ((top - bot) / 2) + bot
		if a.ranges[i].contains(base.addr()) {
			// a.ranges[i]包含基数，所以它的后继者是下一个索引。在这种情况下，我可能实际上是后继者，但我们不能确定，直到我们检查它前面的那些。在这种情况下，我们知道基数是大于或等于a.ranges[i].limit-1，
			return i + 1
		}
		if base.lessThan(a.ranges[i].base) {
			top = i
		} else {
			// 所以我肯定不是继任者。
			// 我们已经检查了i，所以选择下一个
			// /一个。
			bot = i + 1
		}
	}
	// 还有一些顶级机器人候选，所以
	// 对它们进行迭代，发现第一个
	// base严格小于。
	for i := bot; i < top; i++ {
		if base.lessThan(a.ranges[i].base) {
			return i
		}
	}
	return top
}

// findAdrGreaterEqual返回由
// 表示的最小地址，即>=addr。因此，如果地址由a表示，
// 则返回addr。第二个返回值指示
// a中的addr是否存在这样的地址。也就是说，如果addr大于
// a已知的任何地址，则第二个返回值将为false。
func (a *addrRanges) findAddrGreaterEqual(addr uintptr) (uintptr, bool) {
	i := a.findSucc(addr)
	if i == 0 {
		return a.ranges[0].base.addr(), true
	}
	if a.ranges[i-1].contains(addr) {
		return addr, true
	}
	if i < len(a.ranges) {
		return a.ranges[i].base.addr(), true
	}
	return 0, false
}

// contains如果a包含地址addr，则返回true。
func (a *addrRanges) contains(addr uintptr) bool {
	i := a.findSucc(addr)
	if i == 0 {
		return false
	}
	return a.ranges[i-1].contains(addr)
}

// add将新地址范围插入到a。
// 
// r不能与a和r中的任何地址范围重叠。size（）必须大于0。
func (a *addrRanges) add(r addrRange) {
	// 此函数中的副本可能很昂贵，但此数据
	// 结构旨在表示Go堆。在最坏的情况下，假设保守的复制速率为25Gib/s（
	// 需要约160µs，这是完全不连续的~160µs仍然很多，但在实践中，大多数平台都有64个MiB区域（将其减少16倍），Go堆通常大部分是连续的，因此一个addrRanges扩展到该大小的可能性非常低。
	// 复制几乎不会触发页面错误），那么对于一个具有4个MiB 
	// 区域的1TiB堆，复制此

	// 空范围对a表示的地址集
	// 没有影响，但是传递零大小的范围几乎总是一个错误。
	if r.size() == 0 {
		print("runtime: range = {", hex(r.base.addr()), ", ", hex(r.limit.addr()), "}\n")
		throw("attempted to add zero-sized address range")
	}
	// 因为我们假设r当前不在a中表示，所以
	// findSucc为我们提供了插入索引。
	i := a.findSucc(r.base.addr())
	coalescesDown := i > 0 && a.ranges[i-1].limit.equal(r.base)
	coalescesUp := i < len(a.ranges) && r.limit.equal(a.ranges[i].base)
	if coalescesUp && coalescesDown {
		// 我们有邻居，他们都与我们接壤。
		// 将a.ranges[i-1]、r和a.ranges[i]合并为a.ranges[i-1]。
		a.ranges[i-1].limit = a.ranges[i].limit

		// 删除a.ranges[i]。
		copy(a.ranges[i:], a.ranges[i+1:])
		a.ranges = a.ranges[:len(a.ranges)-1]
	} else if coalescesDown {
		// 我们只有一个地址较低的邻居，而且它与我们相邻。
		// 将新空格合并到a.ranges[i-1]中。
		a.ranges[i-1].limit = r.limit
	} else if coalescesUp {
		// 我们只有一个邻居在更高的地址，它与我们相邻。
		// 将新空格合并到a.ranges[i]中。
		a.ranges[i].base = r.base
	} else {
		// 我们可能有也可能没有不与我们接壤的邻居。
		// 添加新范围。
		if len(a.ranges)+1 > cap(a.ranges) {
			// 增加阵列。请注意，这泄漏了旧阵列，但由于
			// 我们将加倍，我们最多有2倍的浪费。对于1tib堆和
			// 4个MiB区域，它们都是不连续的（都是非常保守的
			// /假设），这将浪费最多4个MiB的内存。
			oldRanges := a.ranges
			ranges := (*notInHeapSlice)(unsafe.Pointer(&a.ranges))
			ranges.len = len(oldRanges) + 1
			ranges.cap = cap(oldRanges) * 2
			ranges.array = (*notInHeap)(persistentalloc(unsafe.Sizeof(addrRange{})*uintptr(ranges.cap), sys.PtrSize, a.sysStat))

			// 在旧数组中复制，但为新范围腾出空间。
			copy(a.ranges[:i], oldRanges[:i])
			copy(a.ranges[i+1:], oldRanges[i:])
		} else {
			a.ranges = a.ranges[:len(a.ranges)+1]
			copy(a.ranges[i+1:], a.ranges[i:])
		}
		a.ranges[i] = r
	}
	a.totalBytes += r.size()
}

// removeLast删除并返回a的最高寻址连续范围
// 或该范围的最后N字节，以较小者为准。如果a为
// 空，则返回空范围。
func (a *addrRanges) removeLast(nBytes uintptr) addrRange {
	if len(a.ranges) == 0 {
		return addrRange{}
	}
	r := a.ranges[len(a.ranges)-1]
	size := r.size()
	if size > nBytes {
		newEnd := r.limit.sub(nBytes)
		a.ranges[len(a.ranges)-1].limit = newEnd
		a.totalBytes -= nBytes
		return addrRange{newEnd, r.limit}
	}
	a.ranges = a.ranges[:len(a.ranges)-1]
	a.totalBytes -= size
	return r
}

// RemoveCreateRequal删除addr以上的a的范围，另外
// 拆分包含addr的任何范围。
func (a *addrRanges) removeGreaterEqual(addr uintptr) {
	pivot := a.findSucc(addr)
	if pivot == 0 {
		// 地址在a中所有范围之前。
		a.totalBytes = 0
		a.ranges = a.ranges[:0]
		return
	}
	removed := uintptr(0)
	for _, r := range a.ranges[pivot:] {
		removed += r.size()
	}
	if r := a.ranges[pivot-1]; r.contains(addr) {
		removed += r.size()
		r = r.removeGreaterEqual(addr)
		if r.size() == 0 {
			pivot--
		} else {
			removed -= r.size()
			a.ranges[pivot-1] = r
		}
	}
	a.ranges = a.ranges[:pivot]
	a.totalBytes -= removed
}

// cloneInto将a的状态深度克隆到b中，如果可以的话，重新使用
// b的范围。
func (a *addrRanges) cloneInto(b *addrRanges) {
	if len(a.ranges) > cap(b.ranges) {
		// 增加阵列。
		ranges := (*notInHeapSlice)(unsafe.Pointer(&b.ranges))
		ranges.len = 0
		ranges.cap = cap(a.ranges)
		ranges.array = (*notInHeap)(persistentalloc(unsafe.Sizeof(addrRange{})*uintptr(ranges.cap), sys.PtrSize, b.sysStat))
	}
	b.ranges = b.ranges[:len(a.ranges)]
	b.totalBytes = a.totalBytes
	copy(b.ranges, a.ranges)
}
